Quadratic residuosity problem

The quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number. This is an important consideration in contemporary cryptography.[1]

Contents

Formulation

Given the specific case of N being the product of distinct odd prime numbers p and q, the structure of the squaring map:

a → a2 mod N

on the multiplicative group of invertible residues modulo N, is as a group homomorphism with kernel a Klein group of order four. The image is therefore of size roughly N/4. More precisely, it is of order:

\frac{(p - 1)(q - 1)}{4}

In contrast, the same mapping modulo prime P has the kernel of order 2 and the image of order (P − 1)/2. In this case it is easy to characterize the image computationally, since the Jacobi symbol takes the value +1 precisely on quadratic residues modulo P.

Modulo composite N the corresponding Jacobi symbol characterizes a subgroup of the residues which is larger by factor of two; that is, it rules out roughly half of the residues modulo N, while the problem as posed is to characterize a subset of size a quarter of N. This difference constitutes the quadratic residuosity problem, in this particular but essential case of N being the product of two primes.

The computational hardness assumption is that bridging this gap can only to be done by lengthy calculation, when quantified in terms of the size of N.

Applications

The intractability of the quadratic residuosity problem is the basis for the security of the Blum Blum Shub pseodorandom number generator and the Goldwasser–Micali cryptosystem.[2][3]

See also

Notes

  1. ^ Mathematicians say residuacity: residuosity, something of a malapropism, has been adopted by most cryptographers.
  2. ^ S. Goldwasser, S. Micali (1982). "Probabilistic encryption and how to play mental poker keeping secret all partial information". Proc. 14th Symposium on Theory of Computing: 365–377. doi:10.1145/800070.802212. 
  3. ^ S. Goldwasser, S. Micali (1984). "Probabilistic encryption". Journal of Computer and System Sciences 28 (2): 270–299. doi:10.1016/0022-0000(84)90070-9.